package Test_1212;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Sort {
    //直接插入排序
    //思路：
    //i从1下标元素开始遍历，j为i-1;

    //将j中的元素与tmp中的元素进行比较
         //如果j中的元素大于tmp中的元素，那么将j中的元素放到j+1的元素中
         //如果j中的元素小于tmp中的元素，那么说明j+1是适合tmp元素的位置，将其插入,退出循环
    //最坏的情况下：逆序；
    //最好的情况下：本身有序，越有序越快
    public static  void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            //将下标i中的元素给tmp；
            int tmp=array[i];
            int j = i-1;
            for (; j >=0; j--) {
                //将j中的元素与tmp中的元素进行比较
                //如果j中的元素大于tmp中的元素，那么将j中的元素放到j+1的元素中
                if(tmp<array[j]){
                    array[j+1]=array[j];
                }else{
                    //否则说明j+1是适合tmp元素的位置，将其插入
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    public static  void shellSort(int[] array){
        int gap=array.length;
        while(gap>=1){
            gap=gap/2;
            //gap=gap/3+1;
            shell(array,gap);
        }
    }
    public static  void shell(int[] array,int gap){
        for (int i =gap; i < array.length; i++) {
            //将下标i中的元素给tmp；
            int tmp=array[i];
            int j = i-gap;
            for (; j >=0; j-=gap) {
                //将j中的元素与tmp中的元素进行比较
                //如果j中的元素大于tmp中的元素，那么将j中的元素放到j+1的元素中
                if(tmp<array[j]){
                    array[j+gap]=array[j];
                }else{
                    //否则说明j+1是适合tmp元素的位置，将其插入
                    array[j+gap]=tmp;
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    //选择排序
    public static  void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            //记录最小元素下标
            int minIndex=i;
            for (int j=i+1; j < array.length ; j++) {
                //如果j下标的元素比mid的元素小，将j下标赋值给mid
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            //将i下标与当前的最小值进行交换
            swap(array,i,minIndex);
        }
    }
    public static  void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static  void selectSort2(int[] array){
        int left=0;
        int right= array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i <=right ; i++) {
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
            }
            swap(array,left,minIndex);
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    public static  void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg=false;
            for (int j = i; j < array.length-i-1 ; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(flg==false){
                break;
            }
        }
    }
    public static  void quickSort(int[] array){
        //快速排序入口
        quickNor(array,0,array.length-1);
         // quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        //递归结束条件
        if (start>=end){
            return;
        }
        if(end-start+1<=7){
            insertSortRange(array,start,end);
        }
        int midIndex=getMid(array,start,end);
        swap(array,midIndex,start);
        //划分区间
        int pivot=partition2(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static void quickNor(int[] array,int left,int right){
        Deque<Integer> stack=new ArrayDeque<>();
        //划分区域
        int pivot=partition(array,left,right);
        //将两边的左右区间放入栈中
        if(pivot-1>left){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1<right){
            stack.push(pivot+1);
            stack.push(right);
        }
        //只要栈不为空，就代表还不是整体有序
        while(!stack.isEmpty()){
            //弹出右边界，在弹出左边界
            right=stack.pop();
            left=stack.pop();
            //将左右边界区间在进行分割
            pivot=partition(array,left,right);
            //如果满足条件，在进行入栈
            if(pivot-1>left){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1<right){
                stack.push(pivot+1);
                stack.push(right);
            }
        }        }
    private static void insertSortRange(int[] array,int start,int end){
        for (int i = start+1; i <= end; i++) {
            //将下标i中的元素给tmp；
            int tmp=array[i];
            int j = i-1;
            for (; j >=start; j--) {
                //将j中的元素与tmp中的元素进行比较
                //如果j中的元素大于tmp中的元素，那么将j中的元素放到j+1的元素中
                if(tmp<array[j]){
                    array[j+1]=array[j];
                }else{
                    //否则说明j+1是适合tmp元素的位置，将其插入
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    //Hoare版分割
    public static int partitionHoare(int[] array,int left,int right){
       int tmp=array[left];
       int tmpleft=left;
       while(left<right){
           while(left<right && array[right]>=tmp){
               right--;
           }
           while(left<right && array[left]<=tmp){
                left++;
            }
           swap(array,left,right);
       }
       swap(array,left,tmpleft);
       return left;
    }
    public static int partitionHoare1(int[] array,int left,int right){
        int tmp=array[left];
        int tmpleft=left;
        while(left<right){
            while(left<right && array[left]<=tmp){
                left++;
            }
            while(left<right && array[right]>=tmp){
                right--;
            }
            swap(array,left,right);
        }
        swap(array,left,tmpleft);
        return left;
    }
    //挖坑法
    public static int partition(int[] array,int left,int right){
        int tmp=array[left];
        while(left<right){
            //右指针寻找比tmp小的值给左指针
            while(left<right && array[right]>=tmp){
                right--;
            }
            //将right下标元素给left下标元素
            array[left]=array[right];
            //左指针寻找比tmp大的值给右指针
            while(left<right && array[left]<=tmp){
                left++;
            }
            //将left下标元素给right下标元素
            array[right]=array[left];

        }
        //将基准数给left或者right下标
        array[left]=tmp;
        return left;
    }
    public static int partition2(int[] array,int left,int right){
          int prev=left;
          int cur=left+1;
          while(cur<=right){
              if(array[cur]<array[left] && array[++prev]!=array[cur]){
                  swap(array,cur,prev);
              }
              cur++;
          }
          swap(array,prev,left);
          return prev;
    }
    private static int getMid(int[] array, int left,int right){
        int mid=(left+right)/2;
        //如果left下标小于right下标元素
        if(array[left]<array[right]){
            //比较left与mid
            if(array[left]>array[mid]){
                return left;
            }else if(array[right]<array[mid]){
                //比较right与mid
                return right;
            }else{
                return mid;
            }
            //如果left下标大于right下标元素
        }else{
            if(array[left]<array[mid]){
                return left;
            }else if(array[right]>array[mid]){
                //比较right与mid
                return right;
            }else{
                return mid;
            }
        }
    }
    public static void mergeSort(int[] array){
        mergeSortTmp(array,0,array.length-1);
    }
    //分解
    public static void mergeSortTmp(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        //分解：
        int mid=(left+right)/2;
        mergeSortTmp(array,left,mid);
        mergeSortTmp(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }
    //合并
    public static void merge(int[] array,int left,int mid,int right){
        int[] tmp=new int[right-left+1];
        int k=0;
           int s1=left;
           int s2=mid+1;
           while(s1<=mid && s2<=right){
               if(array[s1]<=array[s2]){
                   tmp[k++]=array[s1++];
               }else{
                   tmp[k++]=array[s2++];
               }
           }
           while(s1<=mid){
               tmp[k++]=array[s1++];
           }
           while(s2<=right){
            tmp[k++]=array[s2++];
           }
           //保证数组有序
        for (int i = 0; i < k; i++) {
            array[i+left]=tmp[i];
        }
        }
}
